package work;

import java.util.Arrays;

public class Test07 {
}
class Solution {
    /**
     * Note: 类名、方法名、参数名已经指定，请勿修改
     *
     *
     *
     * @param arr int整型 一维数组
     * @return int整型
     */
    public int run(int[] arr) {
        // write code here
        int sum = 0, min = Integer.MAX_VALUE;
        for (int i = 0; i < arr.length; i++) {
            sum+=arr[i];
            min = Math.min(min, arr[i]);
        }

        for (int i = min; i <= sum/2; i++) {
            if (sum%i!=0) continue;
            int temp = sum-i;
            if (temp%(arr.length-1)==0) return i;
            boolean[] records = new boolean[arr.length];
            check(arr,i,0,temp,records);
            if (last(records)) return sum/i;

        }

        return 0;
    }

    //判断arr中的数字是否分为和为target的若干子集
    public boolean check(int[] arr ,int target,int start,int sum,boolean[] records) {
        if (sum==target) return true;
        for (int i = start; i < arr.length; i++){
            if (!records[i]&&sum+arr[i]<=target){
                records[i] = true;
                if (check(arr,target,i+1,sum+arr[i],records)) continue;
                records[i] = false;
            }
        }

        return false;
    }

    public boolean last(boolean[] records){
        for (boolean record : records) {
            if (record) return false;
        }
        return true;
    }
}